package nz.ac.massey.groupproject.ecs2;

import java.util.ArrayList;
import java.util.HashSet;

//import java.util.Iterator;
import java.util.NoSuchElementException;


/*
 * This array cheats addition / removal by paying O(1) cost upfront, and paying O(N)
 * later in a "clean up" operation.
 * Compared to an ArrayList, we sacrifice a bit of semantics (see below) in exchange
 * for the performance.  Compared to a HashSet, we preserve order.
 *
 * This array deduplicates elements (i.e. idempotent).
 *
 * This array does NOT support null elements. nulls are treated as deleted elements.
 *
 * On removal, the removed element will be replaced by null.  This is unlike normal
 * lists, in which elements to the right will be shifted left to fill up the empty
 * slot.
 *
 * Iterator, however, will automatically skip nulls.
 *
 * Calling compact() will cause the array to actually shift and fill in empty spaces,
 * eliminating any nulls.
 *
 * Note that this Iterator does not check for element invalidation, unlike normal
 * container iterators.
 *
 * WARNING: this class uses lazy removal.  Until compact() is called, lazy removed
 *          objects are still referenced and not eligible for GC.
 */
public class LazyArraySet<T> implements Iterable<T> {
	// invariant:   elements and elemSet contain the same set of entities
	// invariant:   lazyRemoved is an (improper) subset of elements
	private final ArrayList<T>    elements     = new ArrayList<T>();
	private final HashSet<T>      elemSet      = new HashSet<T>();
	private final HashSet<T>      lazyRemoved  = new HashSet<T>();

	public LazyArraySet() {}
	public LazyArraySet(int initialCapacity) {  elements.ensureCapacity(initialCapacity);  }   // slightly inefficient

	// XXX including the nulls
	public int size() {  return elements.size() - lazyRemoved.size();  }

	public T get(int index) {
		T obj = elements.get(index);  // throws the same exceptions
		if (lazyRemoved.contains(obj)) return null;
		return obj;
	}

	// Return true if added,  false if already exists.
	public boolean add(T obj) {
		if (lazyRemoved.remove(obj)) return true;
		if (!elemSet.add(obj)) return false;
		elements.add(obj);
		return true;
	}

	// Return true if removed,  false if not in array to begin with.
	public boolean remove(T obj) {
		if (! elemSet.contains(obj)) return false;
		return lazyRemoved.add(obj);
	}

	// invalidate all indices
	public void compact() {  compact(false);  }
	public void compact(boolean shrink) {
		// i = new index,  j = old index,  i <= j
		for (int i = 0, j = 0;  j < elements.size(); j++) {
			var obj = elements.get(j);
			if (lazyRemoved.remove(obj))
				elemSet.remove(obj);
			else
				elements.set(i++, obj);
		}
		elements.subList( elemSet.size(), elements.size() ).clear();  // what a great API
		if (shrink) elements.trimToSize();
	}



	public Iterator iterator() {  return new Iterator();  }

	// XXX does NOT check if array is modified during iteration
	public class Iterator implements java.util.Iterator<T> {
		private int nextIndex = 0;

		public boolean hasNext() {  return nextIndex < elements.size();  }

		public T next() {
			while (nextIndex < elements.size()) {
				T obj = elements.get(nextIndex++);
				if (null != obj)
					return obj;
			}
			throw new NoSuchElementException();
		}
	}
}
